//
// Created by francklinson on 2021/10/19 AT 10:57.
//
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <functional>
#include <climits>
#include <string>

using namespace std;

/**
 * 字典树节点
 */
struct TrieNode {
    vector<TrieNode *> child;
    bool isEnd;

    TrieNode() {
        this->child = vector<TrieNode *>(26, nullptr);
        this->isEnd = false;
    }
};

/**
 * 将一个单词插入字典树中
 * @param root
 * @param word
 */
void insert(TrieNode *root, const string &word) {
    TrieNode *node = root;
    for (auto c: word) {
        // 如果原先的字典树上到这里就结束了  那么拓展枝干长度
        if (node->child[c - 'a'] == nullptr) {
            node->child[c - 'a'] = new TrieNode();
        }
        node = node->child[c - 'a'];
    }
    node->isEnd = true; // 标记为true  说明存在这个单词
}

class WordDictionary {
public:
    WordDictionary() {
        trie = new TrieNode();
    }

    void addWord(string word) {
        insert(trie, word);
    }

    bool search(string word) {
        return dfs(word, 0, trie);
    }

    /**
     * 深度优先 搜索字典树中是否存在这个单词
     * @param word   目标单词
     * @param index  当前搜索到这个单词的第几个字母
     * @param node   当前搜索的节点
     * @return
     */
    bool dfs(const string &word, int index, TrieNode *node) {
        if (index == word.size()) {
            return node->isEnd; // 结束条件
        }
        char ch = word[index];
        // 如果这一位是a-z的任意一位，对应取出来  进行下一次搜索
        if (ch >= 'a' && ch <= 'z') {
            TrieNode *child = node->child[ch - 'a'];
            if (child != nullptr && dfs(word, index + 1, child)) {
                return true;
            }
        }// 如果这一位是'.'，那么可以是a-z的任意一位 需要全部搜索一遍
        else if (ch == '.') {
            for (int i = 0; i < 26; i++) {
                TrieNode *child = node->child[i];
                if (child != nullptr && dfs(word, index + 1, child)) {
                    return true;
                }
            }
        }
        return false;
    }

private:
    TrieNode *trie;
};

int main() {
    return 0;
}

